1. Field of the Invention
The present invention relates to tracing technology, and more particularly to a technique for detecting a loop to generate a trace.
2. Related Art
Recently, importance has been given to tracing technology in processing systems for performing dynamic compilation or binary translation (for example, see Vasanth Bala et al., “Dynamo: A Transparent Dynamic Optimization System,” ACM SIGPLAN Notices, Volume 35, pp. 1-12, Can 2000; and Andreas Gal et al., “Trace-based just-in-time type specialization for dynamic languages,” In Programming Languages Design and Implementation, pp. 1-11, ACM, 2009 The tracing technology is a technique for extracting a code path repeatedly passed through during execution of a program, and recording and compiling the trajectory, i.e., the trace thereof to generate fast code.
According to the tracing technology, since only the code actually executed is optimized, problems in conventional compilation techniques used in units of functions (or methods or procedures, hereinafter the same shall apply), such as that actually unused code is optimized and that optimization across functions cannot be achieved or is difficult if it is performed over multiple stages, can be solved or reduced.
Among various compilation methods used in units of traces, the most basic method is practiced as follows: First, source code is converted to intermediate code such as byte code. Next, an interpreter executes the intermediate code and monitors the execution. When a backward branch is detected, the destination of the branch is recorded as a loop starting point candidate. This is because loop processing always involves a backward branch, but the loop starting point candidate can be created on any condition other than the destination of the backward branch. Then, when it is detected that a code path starting with the loop starting point candidate is executed repeatedly predetermined times or more, executed intermediate code (trace) is recorded, and the recorded trace is optimized and compiled to generate native code.
The generated native code is executed directly by the system as long as the same path as the original trace is selected. However, when the precondition is not satisfied, such as, when the results of conditional branching are different, control is returned to the interpreter or shifted to native code generated from another trace. The cost of switching to the interpreter or transition to another trace is high, and this can cause a runtime overhead. Therefore, it is important to detect a loop correctly to generate a trace not to cause switching to the interpreter or transition to another trace frequently.
David Hinikeret et al., “Improving Region Selection in Dynamic Optimization Systems,” Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, pp. 141-154, Nov. 12-16, 2005 discloses a technique for determining a sequence of instructions to be a loop on condition that the addresses of the first instruction and the last instruction in the sequence of instructions are the same.
Andreas Gal et al. discloses an “Incremental Dynamic Code Generation with Trace Trees,” Technical Report, pp. 6-16, Donald Bren School of Information and Computer Science, University of California, Irvine, November 2006, and Duane Merrill et al., “Trace Fragment Selection within Method-based JVMs,” In Proceedings of the International Conference on Virtual Execution Environments, ACM Press, pp. 41-50, 2008 disclose techniques for prohibiting the generation of a trace including a return instruction from a method to which the first instruction of the trace belongs.
Note that Vasanth Bala et al., “Dynamo: A Transparent Dynamic Optimization System,” ACM SIGPLAN Notices, Volume 35, pp. 1-12, Can 2000, mentioned above, is listed as a conventional call stack constructing technique for emulating push/pop operations on a call stack to construct the call stack at the time of each instruction.
U.S. Pat. No. 6,751,789 discloses a “Method and System For Periodic Sampling For Real-Time Generation of Segments of Call Stack Trees Augmented With Call Stack Position Determination.”
Duane Merrill et al. disclose a “Trace Fragment Selection within Method-based JVMs,” In Proceedings of the International Conference on Virtual Execution Environments, ACM Press, pp. 41-50, 2008.